import java.util.PriorityQueue;
import java.util.Comparator;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 定义最小堆，按节点的值排序
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });

        // 将所有链表的头节点加入堆
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(); // 虚拟头节点
        ListNode tail = dummy;

        // 每次从堆中取出最小节点，加入结果链表
        while (!minHeap.isEmpty()) {
            ListNode minNode = minHeap.poll();
            tail.next = minNode;
            tail = minNode;

            // 如果该节点有下一个节点，将下一个节点加入堆
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        return mer(lists,0,lists.length-1);

    }

    public ListNode mer(ListNode[] lists,int left,int right){
        if(left>=right) return lists[left];
        int mid=left+(right-left)/2;
        ListNode l1= mer(lists,left,mid);
        ListNode l2= mer(lists,mid+1,right);
        return merge(l1,l2);

    }

    public ListNode merge(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;

        ListNode phead=new ListNode();
        ListNode tail=phead;



        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                tail.next=l1;
                tail=l1;
                l1=l1.next;
            }else{
                tail.next=l2;
                tail=l2;
                l2=l2.next;

            }
        }

        if(l1!=null) tail.next=l1;
        if(l2!=null) tail.next=l2;

        return phead.next;



    }
}